c++ priority_queue

Posted on   |   In   |  

优先队列的使用

优先队列

优先队列是一种比较常用的结构,但它并不是队列，因为它是用堆(一般是二叉堆)实现的。它的核心操作是支持在常量时间内获得最优先的元素。priority_queue支持push, pop, top这三个核心的操作。
它的模板声明带有三个参数，priority_queue
Type 为数据类型， Container 为保存数据的容器，Functional 为元素比较方式。
Container 必须是用数组实现的容器，比如 vector, deque 但不能用 list.
STL里面容器默认用的是 vector. 比较方式默认用 operator< , 所以如果你把后面俩个参数 缺省的话，优先队列就是大顶堆，队头元素最大.

STL里面定义了一个仿函数 greater<>，对于基本类型可以用这个仿函数声明小顶堆

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>
#include <queue>
using namespace std;
int main(){
    priority_queue<int,vector<int>,less<int> >q;//使用priority_queue<int> q1,使用最小堆时，将上面的less换成greater方法
    for(int i=0;i<10;i++) 
		q1.push(i);
    while(!q1.empty()){
        cout<<q1.top()<< endl;
        q1.pop();
    }
    return 0;
}

上面的less，greater只能针对内部的类型，要想使用less这种类型，就得自定义，有两种方法
(1)自定义重载类型operator<

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <iostream>
#include <queue>
using namespace std;
struct node{
  int x;
  int y;
  node(int a=0, int b=0):x(a), y(b){}
  //最小堆,比较x，相同比较y(也可以将此部分置于结构体外)
  bool operator<(const node &b)const{
    if(x == b.x) return y > b.y;

    return x > b.x;
  }
};
/*最大堆
 struct node{
  int x;
  int y;
  node(int a=0, int b=0):x(a), y(b){}

  bool operator<(const node &b)const{
    if(x == b.x) return y < b.y;

    return x < b.x;
  }
 */
int main(){

  priority_queue<node, vector<node> > q;

  int i;
  for(i=0;i<10;++i){
    q.push(node(i, i + 1));
  }

  q.push(node(5, 0));

  while(!q.empty()){
    cout<<q.top().x<<" "<<q.top().y<<endl;
    q.pop();
  }
  return 0;
}

(2)第二种方法,自定义比较函数(14-18行)
这个自定义比较函数比较好，在set中也可以这样定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#include <queue>


using namespace std;


struct node{
  int idx;
  int key;
  node(int a=0, int b=0):idx(a), key(b){}
};

struct cmp{
  bool operator()(node a, node b){
    return a.key > b.key;
  }
};
int main(){
  
  priority_queue<node, vector<node>, cmp> q;
  
  int i;
  for(i=0;i<10;++i){
    q.push(node(i, i));
  }

  while(!q.empty()){
    cout<<q.top().key<<endl;
    q.pop();
  }
  return 0;
}

参阅
http://www.cnblogs.com/nirvana-phoenix/archive/2012/05/29/2524344.html